/*************************************************************************
> File Name: reverse_polish.h
> Author: chen
> Mail: chen_tmacy@foxmail.com
> Created Time: 2014年07月24日 星期四 17时10分27秒
************************************************************************/

#include"linkstack.h"

char* reverse_polish(char * exp){

    char * ch = (char*)malloc(strlen(exp)); 
    linkstack* s = create_null_linkstack();

    for(int i = 0;(*(ch + i) = *(exp + i)) != '\0';i++)
    ;

    char c = 0;
    int j = 0;
    
    for(int i = 0;(c = *(ch + i)) != '\0';i++){
        if(c >= '0' && c <= '9'){   //是数字，直接输出
            *(exp + j) = c;
            j++;
        }else{
            if(is_linkstack_empty(s) || c == '('){  //栈是空，则直接入栈
                push_linkstack(s,c);
            }
            else{
                if(prior(c) > prior(get_linkstack_top(s))){  //若当前操作符比栈顶操作符优先级高，则入栈
                    push_linkstack(s,c);
                }else if(c == ')'){
                    while(get_linkstack_top(s) != '('){
                       *(exp + j++) = pop_linkstack(s);
                    }
                    pop_linkstack(s);
                }else{
                   while(!is_linkstack_empty(s)){
                       *(exp + j) = pop_linkstack(s);
                       j++;
                   }//否则，循环出栈直到栈空
                    push_linkstack(s,c);
                }
            }
        }
    }

    while(!is_linkstack_empty(s)){
    	*(exp + j) = pop_linkstack(s);
    	j++;
    }
    *(exp + j) = '\0';
    clear_linkstack(s);
    return exp;
}

int prior(char  ch ){

    switch(ch){
        case ')':
        case '(':
            return 0;
        case '+':
        	return 1;
        case '-':
        	return 1;
        case '*':
        	return 2;
        case '/':
        	return 2;
        default:
            printf("error no such opreator :%c \n",ch);
	        return -1;
    }
}
//计算逆波兰表达式的值
int compute(char * exp){
    linkstack * stack; 
    stack = create_null_linkstack();
    int a = 0;
    int b = 0;

    while(*exp){
        if(*exp >= '0' && *exp <= '9'){
            push_linkstack(stack,*exp - '0');
        }else{
            a = pop_linkstack(stack);
            b = pop_linkstack(stack);

            switch(*exp){
                case '+':
                push_linkstack(stack,a + b);
                break;
                case '-':
                push_linkstack(stack,b - a);
                break;
                case '*':
                push_linkstack(stack,a * b);
                break;
                case '/':
                push_linkstack(stack,b / a);
            }
        }
        exp++;
    }
    return get_linkstack_top(stack);
}

